package visualizer.client.algorithms.bst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:26
 */
public class BSTRemovingAlgorithm implements Algorithm {
    private int totalStepCount;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return removeFromBST(tree.copyTree(false), inputValue, step);
    }

    @Override
    public int getStepsCount(BinaryTree tree, int inputValue) {
        totalStepCount = 0;
        removeFromBST(tree.copyTree(false), inputValue, -1);
        return totalStepCount;
    }

    public AlgoResult removeFromBST(BinaryTree bTree, int inputValue, int stepNo) {
        BNode nodeToRemove = new BNode(inputValue);
        BNode theRootNode = bTree.getRoot(), parent = null;

        if (stepNo-- == 0) {
            return new AlgoResult(bTree, "Удаление узла с ключом " + nodeToRemove.getValue());
        }
        if (stepNo-- == 0) {
            return new AlgoResult(bTree, "Сперва узел нужно найти");
        }
        if (theRootNode == null) {
            updateTotalStepCount(stepNo);
            return new AlgoResult(bTree, "Дерево пусто, узла с ключом " + nodeToRemove.getValue() + " не существует");
        }

        while (true) {
            int cmp = nodeToRemove.getValue().compareTo(theRootNode.getValue());
            if (cmp == 0) {
                if (stepNo-- == 0) {
                    theRootNode.setInnerColor("lightgreen");
                    theRootNode.setOuterColor("green");
                    return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ " + nodeToRemove.getValue() + " равен ключу " + theRootNode.getValue() + ", узел найден");
                }
                break;
            } else {
                parent = theRootNode;
                if (cmp < 0) {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ " + nodeToRemove.getValue() + " меньше ключа " + theRootNode.getValue() + ", обрабатываем левое поддерево");
                    }
                    if (theRootNode.getLeftBNode() == null) {
                        if (stepNo-- == 0) {
                            theRootNode.setOuterColor("red");
                            return new AlgoResult(bTree, "У узла нет левого потомка, узла с ключом " + nodeToRemove.getValue() + " не существует");
                        }
                        updateTotalStepCount(stepNo);
                        return new AlgoResult(bTree, "Узла с ключом " + nodeToRemove.getValue() + " не существует");
                    }
                    theRootNode = theRootNode.getLeftBNode();
                } else {
                    if (stepNo-- == 0) {
                        theRootNode.setOuterColor("red");
                        return new AlgoResult(bTree, "Сравниваем ключи в узлах: ключ  " + nodeToRemove.getValue() + " больше ключа " + theRootNode.getValue() + ", обрабатываем правое поддерево");
                    }
                    if (theRootNode.getRightBNode() == null) {
                        if (stepNo-- == 0) {
                            theRootNode.setOuterColor("red");
                            return new AlgoResult(bTree, "У узла нет правого потомка, узла с ключом " + nodeToRemove.getValue() + " не существует");
                        }
                        updateTotalStepCount(stepNo);
                        return new AlgoResult(bTree, "Узла с ключом " + nodeToRemove.getValue() + " не существует");
                    }
                    theRootNode = theRootNode.getRightBNode();
                }
            }
        }

        theRootNode.setInnerColor("lightgreen");
        theRootNode.setOuterColor("green");

        if (stepNo-- == 0) {
            return new AlgoResult(bTree, "Теперь приступим к удалению");
        }

        if (theRootNode.getRightBNode() == null) {
            if (stepNo-- == 0) {
                if (theRootNode.getLeftBNode() != null) {
                    return new AlgoResult(bTree, "У узла с ключом " + nodeToRemove.getValue() + " есть только левый потомок, поэтому просто соединяем его родителя и его левого потомка напрямую");
                } else {
                    return new AlgoResult(bTree, "У узла с ключом " + nodeToRemove.getValue() + " нет потомков, поэтому просто удаляем его из дерева");
                }
            }
            if (parent == null) {
                bTree.setRootNode(theRootNode.getLeftBNode());
            } else {
                if (theRootNode == parent.getLeftBNode()) {
                    parent.setLeftBNode(theRootNode.getLeftBNode());
                } else {
                    parent.setRightBNode(theRootNode.getLeftBNode());
                }
            }
        } else {
            BNode leftMost = theRootNode.getRightBNode();
            parent = null;
            if (stepNo-- == 0) {
                leftMost.setOuterColor("red");
                return new AlgoResult(bTree, "У узла с ключом " + nodeToRemove.getValue() + " есть правый потомок, поэтому найдем в правом поддереве узел с наименьшим ключом");
            }
            while (leftMost.getLeftBNode() != null) {
                parent = leftMost;
                leftMost = leftMost.getLeftBNode();
            }
            if (stepNo-- == 0) {
                leftMost.setInnerColor("lightgreen");
                leftMost.setOuterColor("green");
                return new AlgoResult(bTree, "Узел с наименьшим ключом найден. Ставим его на место удаляемого узла");
            }
            if (parent != null) {
                parent.setLeftBNode(leftMost.getRightBNode());
            } else {
                theRootNode.setRightBNode(leftMost.getRightBNode());
            }
            theRootNode.setValue(leftMost.getValue());
        }

        updateTotalStepCount(stepNo);
        return new AlgoResult(bTree, "Узел с ключом " + nodeToRemove.getValue() + " был успешно удален");
    }

    private void updateTotalStepCount(int stepNo) {
        if (stepNo < 0) {
            totalStepCount = -stepNo;
        }
    }
}
